#ifndef MIN_LIST_H
#define MIN_LIST_H

#include <iostream>
#include <cstring>

using namespace std;

#define FLAG_VISITED 0b01 //表示是否访问过该节点的邻居
// #define FAT_MINLIST_ENTRY //解除注释后，将记录父节点id，root_node_id，hop等信息

// 定义链表节点结构体
struct MinListEntry {
    int id;
    float distance;
    int flag; // 用于标记，例如是否访问过了
    #ifdef FAT_MINLIST_ENTRY
    int parent_node_id; //标记该点的父节点id，用于在图遍历时判断各个点的贡献度
    int root_node_id; //标记该点的初始出发点，用于追踪L2的结果是L1中的哪些点产生的
    int hop; //标记从root到该点进行了几跳
    #endif
};

// 定义最小链表类
class MinList {
private:
    int size;               // 链表总容量
    int count;              // 当前链表实际存储的元素数量
    MinListEntry* entries;  // 存储元素的数组

    // 比较两个元素的距离大小。
    // 建议调用方法为A是查询点，B是链表内的点。返回1不插入，返回0表示插入
    // 使得A的距离等于B时也进行插入，让新点覆盖旧点更有意义。
    int compare(const MinListEntry* A, const MinListEntry* B) const {
        if (A == nullptr || B == nullptr)
            return -1;

        if (A->distance > B->distance)
            return 1;
        return 0;
    }

public:
    // 构造函数，初始化链表
    MinList(int size) : size(size), count(0) {
        entries = new MinListEntry[size];
        std::memset(entries, 0, size * sizeof(MinListEntry));
    }

    // 析构函数，释放链表占用的内存
    ~MinList() {
        delete[] entries;
    }

    // 插入元素到链表中
    int insert(MinListEntry* entry) {
        if (entry == nullptr || entries == nullptr )
            return -1;

        // 0. 首先是判断这个数据是否之前出现过
        for (int i = 0; i < count; i++) {
            if (entry->id == entries[i].id) {
                return -1;
            }
        }

        // 1. 给新数据找到位置
        int index = -1;
        if (count < size) { // 没有填满，直接插入在末尾即可
            index = count;
            count++;
        }
        else { // 填满了，那么和末尾的数据比较，如果比末尾数据小的话直接占领末尾数据的位置即可
            if (compare(entry, &entries[size - 1]) == 0)
                index = size - 1;
            else
                return -1;
        }

        // 2. 拷贝数据
        std::memcpy(&entries[index], entry, sizeof(MinListEntry));

        // 3. 然后把新数据插入到链表中
        // 复杂度为 O(n/2)。虽然是 O(n) 的但是候选列表一般不会很长(通常 10 - 50)，O(n/2) 相比 O(logn) 增加的时间不是很多
        MinListEntry tmp; // 用于交换
        for (int i = 0; i < count - 1; i++) {
            if (compare(&entries[index], &entries[index - 1]) == 0) {
                std::memcpy(&tmp, &entries[index], sizeof(MinListEntry));
                std::memcpy(&entries[index], &entries[index - 1], sizeof(MinListEntry));
                std::memcpy(&entries[index - 1], &tmp, sizeof(MinListEntry));

                index--; // 当前新数据在 index
            }
            else {
                return index;
            }
        }

        return 0;
    }

    //从某个位置开始进行排序。用于当更新了某个元素之后，需要重新排序
    //这里只负责把某个元素的位置放置到合适位置，不是对整个列表进行排序，复杂度为O(n)
    void sort_by_index(int index) {
        if (count <= 1 || index < 0 || index >= count) {
            return; // 边界情况：不需要排序或索引无效
        }

        // 向前冒泡：元素变小时向前移动
        while (index > 0) {
            // 使用 compare 函数进行比较：entries[index] 是待调整元素，entries[index-1] 是其前驱
            if (compare(&entries[index], &entries[index-1]) == 0) { // 小于或等于时返回0，需要交换
                // 交换元素
                MinListEntry tmp;
                memcpy(&tmp, &entries[index], sizeof(MinListEntry));
                memcpy(&entries[index], &entries[index-1], sizeof(MinListEntry));
                memcpy(&entries[index-1], &tmp, sizeof(MinListEntry));
                index--;
            } else {
                break; // 当前元素 >= 前驱元素，停止前移
            }
        }

        // 向后冒泡：元素变大时向后移动
        while (index < count - 1) {
            // 注意：这里比较时，新元素是entries[index]，链表中的后一个是entries[index+1]
            if (compare(&entries[index+1], &entries[index]) == 0) { // 后面元素更小，需要交换
                MinListEntry tmp;
                memcpy(&tmp, &entries[index], sizeof(MinListEntry));
                memcpy(&entries[index], &entries[index+1], sizeof(MinListEntry));
                memcpy(&entries[index+1], &tmp, sizeof(MinListEntry));
                index++;
            } else {
                break; // 当前元素 <= 后继元素，停止后移
            }
        }
    }

    //更新某个位置上元素的值
    //主要是针对DiskANN这种，先用PQ算了一个距离之后用原始向量重新算了一个距离来提高精度
    //这个函数就简单的更新距离值，不作重排序.等下次insert的时候重新排序，因为这是遍历过程中调用的，遍历时修改了顺序的话可能会导致后续出错。
    void update_entry_by_index(int index, float distance){
        if(index >= count){
            cout << "Error, MinList::update_entry index error: " << index << endl;
            exit(0);
        }
        entries[index].distance = distance;
        sort_by_index(index);
    }

    //更新某个id对应的元素，用于位置会改变的情况
    void update_entry_by_id(int id, float distance){
        for(int i = 0; i < count; i++){
            if(entries[i].id == id){
                entries[i].distance = distance;
                sort_by_index(i);
                return;
            }
        }
    }

    //把结果写入到一个数组里面便于处理
    int write_id_to_list(int* list){
        for(int i = 0; i < count; i++){
            list[i] = entries[i].id;
        }
        return 0;
    }

    #ifdef FAT_MINLIST_ENTRY
    int write_parent_id_to_list(int* list){
        for(int i = 0; i < count; i++){
            list[i] = entries[i].parent_node_id;
        }
        return 0;
    }
    #endif

    float get_distance(int index) const {
        return entries[index].distance;
    }

    float get_distance_by_id(int id) const {
        for(int i = 0; i < count; i++){
            if(entries[i].id == id){
                return entries[i].distance;
            }
        }
        return 0.0;
    }

    // 获取链表中的元素数组
    MinListEntry* get_mins() {
        return entries;
    }

    // 获取指定索引处元素的 id
    int get_id(int index) const {
        if(index >= count)
            return -1;
        return entries[index].id;
    }

    // 将某个下标的id设置为指定值，主要用于两层之间的映射
    int set_id(int index, int id) {
        entries[index].id = id;
        return 0;
    }

    #ifdef FAT_MINLIST_ENTRY
    int get_parent_id(int index) const {
        return entries[index].parent_node_id;
    }

    int set_parent_id(int index, int parent_id) {
        entries[index].parent_node_id = parent_id;
        return 0;
    }

    int get_root_id(int index) const {
        return entries[index].root_node_id;
    }

    int get_hop(int index) const {
        return entries[index].hop;
    }

    int reset_node() { //将每个点的root_node_id都设置为id，表明该点是来自于该点;同时将每个点的hop都设置为0
        for (int i = 0; i < count; i++) {
            entries[i].root_node_id = entries[i].id;
            entries[i].hop = 0;
        }
        return 0;
    }
    #endif

    int get_size() const {
        return size;
    }

    int get_count() const {
        return count;
    }

    void set_visited(int index) const {
        entries[index].flag |= FLAG_VISITED;
    }

    int is_visited(int index) const {
        return entries[index].flag & FLAG_VISITED;
    }

    // 打印链表中的元素
    void print() const {
        std::cout << "minlist:";
        for (int i = 0; i < size; i++) {
            std::cout << "(" << entries[i].id << ":" << entries[i].distance << ")-";
        }
        std::cout << std::endl;
    }

    #ifdef FAT_MINLIST_ENTRY
    //打印链表中点的所有字段，每个字段一行，并且注意对齐
    void print_all() const {
        const int FIELD_WIDTH = 16;  // 统一字段宽度
        
        std::cout << "minlist:" << std::endl;
        
        // 打印表头
        std::cout << std::left
                << std::setw(FIELD_WIDTH) << "id"
                << std::setw(FIELD_WIDTH) << "distance"
                << std::setw(FIELD_WIDTH) << "flag"
                << std::setw(FIELD_WIDTH) << "parent_node_id"
                << std::setw(FIELD_WIDTH) << "root_node_id"
                << std::setw(FIELD_WIDTH) << "hop"
                << std::endl;
        
        // 打印分隔线
        std::cout << std::string(FIELD_WIDTH * 7, '-') << std::endl;

        // 打印每个节点的数据
        for (int i = 0; i < size; i++) {
            std::cout << std::left
                    << std::setw(FIELD_WIDTH) << entries[i].id
                    << std::setw(FIELD_WIDTH) << entries[i].distance
                    << std::setw(FIELD_WIDTH) << entries[i].flag
                    << std::setw(FIELD_WIDTH) << entries[i].parent_node_id
                    << std::setw(FIELD_WIDTH) << entries[i].root_node_id
                    << std::setw(FIELD_WIDTH) << entries[i].hop
                    << std::endl;
        }
    }

    //传入一个list（l1的id的数组），计算每一项的root_node_id对应的下标，然后返回最大值（表示最多到第几个候选者是有意义的）
    int get_max_root_node_id_index_in_last_layer(int* list) const { 
        int max_index = 0;
        for (int i = 0; i < size; i++) { //对于每一项root_node_id
            int index = -1;
            for (int j = 0; j < size; j++) { 
                if (entries[i].root_node_id == list[j]) {
                    index = j;
                    break;
                }
            }
            if (index == -1) {
                std::cout << "Error, MinList::print_all can not find root_node_id " << list[i];
                exit(0);
            }
            max_index = std::max(index, max_index);
        }
        return max_index;
    }

    //和上一个的区别是，传入一个l1的id数组，打印出每个root_node_id对应的数组的下标
    void print_all(int* list) const {
        //查找每个root_node_id对应的数组的下标，存到数组中；如果查找不到则报错
        int* index_list = new int[size];
        for (int i = 0; i < size; i++) { //对于每一项root_node_id
            int index = -1;
            for (int j = 0; j < size; j++) { 
                if (entries[i].root_node_id == list[j]) {
                    index = j;
                    break;
                }
            }
            if (index == -1) {
                std::cout << "Error, MinList::print_all can not find root_node_id " << list[i];
                exit(0);
            }
            index_list[i] = index;
        }

        const int FIELD_WIDTH = 16;  // 统一字段宽度
        
        std::cout << "minlist:" << std::endl;
        
        // 打印表头
        std::cout << std::left
                << std::setw(FIELD_WIDTH) << "id"
                << std::setw(FIELD_WIDTH) << "distance"
                << std::setw(FIELD_WIDTH) << "flag"
                << std::setw(FIELD_WIDTH) << "parent_node_id"
                << std::setw(FIELD_WIDTH) << "root_node_id"
                << std::setw(FIELD_WIDTH) << "hop"
                << std::setw(FIELD_WIDTH) << "root_node_in_list"
                << std::endl;
        
        // 打印分隔线
        std::cout << std::string(FIELD_WIDTH * 7, '-') << std::endl;

        // 打印每个节点的数据
        for (int i = 0; i < size; i++) {
            std::cout << std::left
                    << std::setw(FIELD_WIDTH) << entries[i].id
                    << std::setw(FIELD_WIDTH) << entries[i].distance
                    << std::setw(FIELD_WIDTH) << entries[i].flag
                    << std::setw(FIELD_WIDTH) << entries[i].parent_node_id
                    << std::setw(FIELD_WIDTH) << entries[i].root_node_id
                    << std::setw(FIELD_WIDTH) << entries[i].hop
                    << std::setw(FIELD_WIDTH) << index_list[i]
                    << std::endl;
        }
    }
    #endif
};

#endif